package org.example.Soution002;

public class findMidInTwo2 {
    public static void main(String[] args) {
        int[] n1=new int[]{1,2};
        int[] n2=new int[]{3,4};
        findMidInTwo obj=new findMidInTwo();
        System.out.println(obj.findMedianSortedArrays(n1, n2));
    }

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        //确定要找的中位数
        int all=nums1.length+nums2.length;
        if(all%2==1){
            //单数
            int mid=all/2;
            return findKthNum(nums1,nums2,mid+1);
        }else{
            //双数
            int mid=all/2-1;
            return (findKthNum(nums1,nums2,mid+1)+findKthNum(nums1,nums2,mid+2))/2.0;
        }
    }

    public double findKthNum(int[] nums1, int[] nums2, int k) {
        int length1 = nums1.length,length2 = nums2.length;
        int index1=0,index2=0;

        while(true){
            //边界
            //一个数组全比另外一个数组小
            if(index1==length1) return nums2[index2+k-1];//这里的-1是因为还要算上index本身（偷偷+1）
            if(index2==length2) return nums1[index1+k-1];
            //结果边界
            if(k==1) return Math.min(nums1[index1],nums2[index2]);

            //正常情况
            int half=k/2;
            int newIndex1=Math.min(index1+half,length1)-1;//-1是因为要算下标
            int newIndex2=Math.min(index2+half,length2)-1;
            if(nums1[newIndex1]<=nums2[newIndex2]){
                k-=newIndex1-index1+1;
                index1=newIndex1+1;
            }else{
                k-=newIndex2-index2+1;
                index2=newIndex2+1;
            }

        }
    }
}
